#pragma once

#include<iostream>
using namespace std;
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<stack>

template<class W>
struct Edge
{
	int _srci;
	int _dsti;// 目标点的下标
	W _w;// 权值
	Edge* _next;

	Edge(int srci,int dsti,const W& w)
		:_w(w)
		,_srci(srci)
		,_dsti(dsti)
		,_next(nullptr)
	{}

	Edge(int dsti, const W& w)
		:_w(w)
		, _srci(-1)
		, _dsti(dsti)
		, _next(nullptr)
	{}

	bool operator>(const Edge& e) const
	{
		return _w > e._w;
	}

};

// W = weight 权值
template<class V,class W,bool Direction = false>
class Graph
{
	typedef Edge<W> Edge;
	typedef Graph<V, W, Direction> Self;
public:
	Graph(const V* a, size_t n)
	{
		_tables.resize(n,nullptr);
		for (size_t i = 0; i < n; ++i)
		{
			_vertex.push_back(a[i]);
			_indexMap[a[i]] = i;
		}
	}

	size_t GetVertexIndex(const V& v)
	{
		auto it = _indexMap.find(v);
		if (it != _indexMap.end())
		{
			return it->second;
		}
		else
		{
			throw invalid_argument("顶点不存在");
			return -1;
		}
	}


	void AddEdge(const V& src, const V&dst, const W& w)
	{
		int srci = GetVertexIndex(src);
		int dsti = GetVertexIndex(dst);
		Edge* eg = new Edge(srci, dsti, w);
		eg->_next = _tables[srci];
		_tables[srci] = eg;
		if (Direction == false)
		{
			Edge* eg = new Edge(dsti, srci, w);
			eg->_next = _tables[dsti];
			_tables[dsti] = eg;
		}
	}

	void _AddEdge(const size_t& srci, const size_t& dsti, const W& w)
	{
		Edge* eg = new Edge(srci,dsti, w);
		eg->_next = _tables[srci];
		_tables[srci] = eg;
		if (Direction == false)
		{
			Edge* eg = new Edge(dsti,srci, w);
			eg->_next = _tables[dsti];
			_tables[dsti] = eg;
		}
	}

	void Print()
	{
		// 顶点
		for (size_t i = 0; i < _vertex.size(); ++i)
		{
			cout << "[" << i << "]" << "->" << _vertex[i] << endl;
		}
		cout << "-------------------------------" << endl;
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			cout << "[" << _vertex[i] << "-" << i << "-]->";
			Edge* cur = _tables[i];
			while (cur)
			{
				cout << "[" << _vertex[cur->_dsti] << "-" << i << "-" << cur->_w << "]->";
				cur = cur->_next;
			}
			cout << "nullptr" << endl;
		}
	}

	// 广度优先遍历(使用队列，类比树的层序遍历)
	void BFS(const V& src)
	{
		size_t srci = GetVertexIndex(src);
		queue<int> q;
		vector<bool> visited(_vertex.size(),false);
		q.push(srci);
		visited[srci] = true;
		size_t n = _vertex.size();
		size_t vn = 0;
		while (vn < n)
		{
			int levelsize = 1;// 使用levelsize分层打印
			while (!q.empty())
			{
				int _levelsize = levelsize;
				for (int i = 0; i < _levelsize; ++i)
				{
					int _srci = q.front();
					q.pop();
					levelsize--;
					vn++; // 遍历过的顶点数量++；
					Edge* cur = _tables[_srci];
					cout << "[" << _vertex[_srci] << "-" << i << "] ";
					while (cur)
					{
						if (visited[cur->_dsti] != true)
						{
							q.push(cur->_dsti);
							visited[cur->_dsti] = true;
							levelsize++; // 下一层需要遍历顶点数量++
						}
						cur = cur->_next;
					}
				}
				cout << endl;
			}
			cout << endl;
			for (int i = 0; vn < n; ++i) // 如果不是连通图，把剩下的顶点遍历完
			{
				if (visited[i] == false)
				{
					q.push(i);
					visited[i] = true;
					break;
				}
			}
		}
	}

	// 深度优先遍历
	void _DFS(const size_t srci,Edge* eg,vector<bool>& visited)
	{
		cout << "[" << _vertex[srci] << "-" << srci << "]" << "->";
		visited[srci] = true;
		Edge* cur = eg;
		while (cur)
		{
			if (visited[cur->_dsti] == false)
 				_DFS(cur->_dsti, _tables[cur->_dsti], visited); // 这几个传参很重要
			cur = cur->_next;
		}
	}

	void DFS(const V& src)
	{
		size_t srci = GetVertexIndex(src);
		vector<bool> visited;
		visited.resize(_vertex.size());
		_DFS(srci, _tables[srci], visited);
		cout << "nullptr" << endl;
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (visited[i] == false)
			{
				_DFS(i, _tables[i], visited);
				cout << "nullptr" << endl;
			}
		}
	}

	// 最小生成树
	// Kruskal算法
	void Kruskal()
	{
		priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
		//....
	}

	// Prim算法
	int Prim(Self& mintree,const V& v)
	{
		vector<bool> X(_vertex.size(),false);
		vector<bool> Y(_vertex.size(),true);
		int srci = GetVertexIndex(v);
		X[srci] = true;
		Y[srci] = false;
		int size = _vertex.size() - 1;
		int weight = 0;
		while (size--)
		{
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
			for (size_t i = 0; i < X.size(); ++i)
			{
				if (X[i] == true) // 保证是从X集合中的点出发连接的边
				{
					Edge* cur = _tables[i];
					while (cur)
					{
						if (X[cur->_dsti] == false) // 只有当目标顶点不在X上才入队列（保证连接该边不成环）
						{
							pq.push(Edge(cur->_srci, cur->_dsti, cur->_w));
						}
						cur = cur->_next;
					}
				}
			}
			Edge eg = pq.top();
			mintree._AddEdge(eg._srci, eg._dsti, eg._w);
			weight += eg._w;
			X[eg._dsti] = true;
			Y[eg._dsti] = false;
		}
		return weight;
	}

private:
	vector<V> _vertex; // 顶点集合
	map<V, int> _indexMap; // 顶点映射下标 
	vector<Edge*> _tables; // 邻接表
};
